package leetcode_2301_2400;

public class LeeCode_2327 {
    public static void main(String[] args) {
//        System.out.println(peopleAwareOfSecret(6, 2, 4));
//        System.out.println(peopleAwareOfSecret(4, 1, 3));
        System.out.println(peopleAwareOfSecret(999,22,55));
    }
    private static int peopleAwareOfSecret(int n, int delay, int forget) {
        long[][] dp = new long[n + 1][forget + 1];
        dp[1][1] = 1;
        long mod = 1000_000_000 + 7;
        long sum = dp[1][delay];
        for (int i = 2; i <= n; i++) {
            dp[i][1] = sum;
            if (forget - 1 >= 0) System.arraycopy(dp[i - 1], 1, dp[i], 2, forget - 1);
            sum += dp[i][delay];
            sum += mod;
            sum -= dp[i][forget];
            sum %= mod;
        }
        long ans = 0;
        for (int i = 0; i < dp[n].length; i++) {
            ans += dp[n][i];
            ans %= mod;
        }
        return (int) ans;
    }
}
